package tree;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    // 二叉树的非递归 前序遍历实现
    public static void preOrder(TreeNode root){
        if(root == null) return ;
        // 前序遍历实现在遍历的角度看 即第一次遇到 就操作这个节点
        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                System.out.printf("%c ",cur.val); // 第一次遇到就打印!
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return ;
    }


    public static void inOrder(TreeNode root){
        if(root == null) return ;

        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.printf("%c ",top.val); // 从栈中抛出来明显是第二次遇到!
            cur = top.right;
        }
        return ;
    }


    public static void postOrder(TreeNode root){
        if(root == null) return ;

        TreeNode cur = root;
        TreeNode prevPop = null;
        // 第三次被访问到的可能 原因 遍历到null 返回
        // 要么从其右子树返回!
        Deque<TreeNode> stack = new LinkedList<>();

            while(cur != null || !stack.isEmpty()){
                while(cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode top = stack.peek();
                if(top.right == null){
                    System.out.printf("%c ",top.val); // 算作第三次访问到当前节点!
                    stack.pop();
                    prevPop = top; // 更新!
                }else if(prevPop == top.right){
                    System.out.printf("%c ",top.val); // 算作第三次访问到当前节点!
                    stack.pop();
                    prevPop = top; // 更新!
                }else cur = top.right;

            }
            return ;
    }




    public static TreeNode buildTree(){
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');

        a.left = b; a.right = c;
        b.left = d; b.right = e;
        e.right = h; c.left = f;
        c.right = g;
        return a;
    }

    public static void main(String[] args) {
        // todo
        TreeNode root = buildTree();
        preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);
    }

}
